n=250;
m=1000;
k=2000;
D=[42,27,6,11,3,48,46,25,2,33,10,14,9,20,4,15,36,33,1,18,25,44,25,9,40,3,21,23,18,1,2,18,35,7,20,2,13,9,20,50,3,21,7,6,5,28,26,39,20,19,44,43,14,11,26,12,11,27,3,15,29,13,27,3,28,16,38,33,25,31,22,13,17,43,42,36,47,36,31,15,10,8,39,1,46,31,7,32,11,32,15,14,50,37,5,35,3,28,25,19,46,47,12,45,22,36,27,47,49,44,13,14,26,36,49,39,22,5,4,50,23,34,49,5,23,5,35,14,11,3,28,13,5,31,12,11,45,15,4,30,45,40,20,3,27,13,21,43,46,50,17,14,39,29,21,26,1,17,19,15,41,28,44,19,24,38,7,29,5,30,1,9,40,1,4,42,24,48,13,27,6,22,15,8,50,50,38,1,27,14,37,41,19,1,48,43,5,3,36,8,19,7,23,9,7,19,5,46,18,8,9,43,19,41,49,34,33,46,25,47,27,29,6,22,1,34,35,16,25,12,3,24,33,29,25,12,38,5,7,38,9,1,28,48,47,50,40,15,10];
T=[3177,3500,525,464,399,637,26,1,98,373,2256,176,124,706,198,399,2073,1303,281,4383,71,3668,5,5434,39,206,3728,256,95,841,1578,6730,1,309,311,1,437,178,765,5053,740,22,355,2493,176,319,788,460,5300,1,126,10,2205,2334,622,398,2013,26,1170,38,3864,690,1127,114,4725,2610,1761,971,68,637,3578,574,1564,6937,65,348,1976,20,1569,1907,346,871,391,2153,32,100,806,1863,353,357,1,1,40,1189,5600,1902,1124,196,2410,55,196,897,2502,305,2343,423,334,1122,402,205,643,1587,3321,917,677,837,201,637,1711,1501,171,254,60,1456,298,8650,1448,40,66,716,858,1028,537,2358,1377,2067,488,1737,264,809,3962,245,529,570,7760,1903,2015,70,1530,219,1,84,893,9937,239,806,1739,666,476,9002,807,1123,521,5584,4977,6239,2099,1496,1422,885,901,3842,1088,2564,1,911,2187,8132,2603,1352,4037,289,269,658,982,527,402,3,448,1008,400,552,26,1152,1,1798,3738,211,3637,2352,3772,1043,639,1745,414,895,425,1,1869,594,1553,3099,360,222,113,161,938,284,2247,348,3126,3505,15,412,4007,1,554,140,2568,1480,180,128,158,70,54,3325,370,426,170,51,77,26,1376,1798,505,292,335,440,886,5919,478,4,5090,100,1330,3966,95,810,1,100,2700,715,1553,145,12,221,233,1,739,856,405,506,1976,1694,149,754,3198,66,1529,14,536,3078,696,978,727,863,690,1061,531,211,12,5674,1,2957,2017,115,22,109,1,1048,1819,809,1767,795,1716,1776,6125,682,1137,2276,3078,1750,5905,134,1,154,1542,3906,79,1761,206,1983,75,1097,572,3734,2584,3799,897,767,6050,1504,251,2625,2247,1755,20,1549,443,3512,116,1043,8969,48,3889,10,245,380,1016,1107,2644,44,3305,2512,466,2147,132,1,5510,24,3344,400,2537,5798,4034,841,501,782,3136,869,1720,366,1415,467,351,1207,1130,4871,716,333,231,4986,1780,1503,219,2997,464,834,1,1259,5662,2000,1926,14,1,138,437,4560,4863,7099,107,2733,1074,1992,423,1239,4548,30,69,6300,4325,3578,92,461,1978,1457,42,6543,933,1027,1067,635,5374,3170,1456,419,196,1068,9174,1080,1561,1879,735,7,574,607,93,1390,6,4564,1,4030,360,2507,1730,1678,241,1859,86,789,178,1667,2743,1641,4628,544,295,256,688,27,1192,25,1916,4587,1465,641,1,3589,888,82,546,673,2529,780,3435,7805,2086,111,1332,3561,5521,906,1304,2861,5735,494,468,1841,1825,5528,2221,143,1,411,301,1,302,92,311,24,6290,915,1871,3922,327,182,1932,1654,119,220,842,5757,1395,330,1395,1154,149,1908,507,7028,16,128,2674,62,592,24,1569,613,12,3137,98,1152,2243,3799,181,274,4867,3972,498,2410,208,1626,947,785,6554,1609,580,88,191,706,21,1124,2340,288,228,402,2920,744,3903,5334,1639,2312,283,153,569,1319,378,227,229,66,2170,1747,3916,7941,110,175,477,327,1384,301,73,717,175,3484,1943,1134,2218,122,1002,4751,1727,1699,693,2417,6157,1585,684,180,13,519,1080,1764,453,2465,1205,91,742,26,3780,11,3180,307,4242,93,2954,296,8233,133,59,32,561,1361,318,16,56,233,1633,1824,146,31,1934,1770,450,3500,2658,1,6,78,2304,10097,920,635,207,38,135,301,1593,1504,1594,3029,5540,1001,285,1585,1044,2523,3749,723,221,4735,678,1,3568,776,55,4427,3200,1469,1278,664,9630,4315,140,64,1942,312,919,1254,445,107,539,4421,1218,253,1275,1785,2902,3889,6770,175,3004,206,1551,2330,1,1786,85,2936,589,508,1933,263,179,830,5711,1412,7084,1748,3150,1265,1467,1390,2600,431,1559,87,2905,216,1149,1058,133,1187,387,1620,740,1,671,427,1976,699,2488,1259,555,383,666,42,95,2119,998,520,701,2116,123,598,397,42,168,1715,31,1578,773,884,99,9490,4953,441,2,1091,2321,1,834,34,154,342,4564,956,1522,2828,778,29,2447,2167,467,1774,65,7376,3307,1518,852,1,61,4829,1942,7392,1585,6324,1205,367,200,6293,50,1449,8041,491,2648,57,3268,1247,1754,3745,496,52,260,1420,2108,1447,24,1466,367,771,2450,5753,2686,1661,2665,6657,3303,262,5,1040,1577,2843,3725,35,2143,1879,838,1176,3394,5050,2599,2262,285,674,216,940,1670,2818,580,753,3826,55,465,1056,417,278,69,31,1459,112,1766,5565,3006,192,10,434,228,85,224,1,2560,295,2719,562,1530,605,164,90,4242,80,122,5889,251,2744,792,51,9307,2991,896,488,5560,433,174,1366,1131,2063,1386,937,2136,2328,3109,264,658,4282,1110,2571,1480,968,1266,1647,880,178,7003,100,3154,1287,3716,545,2951,69,1056,158,6444,230,288,7746,80,15,4083,101,927,1,10025,456,2896,4707,3839,1023,1104,55,738,2347,628,858,180,193,998,688,215,144,2176,793,1003,5559,32,2643,1,5821,1,177,656,1968,1,9104,1,1408,248,983,48,789,1052,736,852,2054,103,2419,4426,5777,493,1295,8,218,554,1,189,2128,13,494,4615,492,335,1,2742,2469,407,2299,1533,4414,646,3859,4316,4628,552,733,6074,2522,57,3670,3685,737];
A=[67,109,46,48,102,47,8,1,106,17,72,110,23,19,7,35,128,153,36,133,3,120,99,123,12,11,84,171,110,30,75,156,1,9,119,1,12,5,23,125,26,2,10,56,14,57,62,50,151,1,13,2,48,92,29,45,169,9,26,2,88,17,75,4,181,61,80,47,144,15,135,50,59,181,68,11,53,5,59,42,43,42,38,90,3,7,28,49,22,22,1,1,14,62,119,94,34,12,86,3,113,27,74,15,72,41,49,61,13,21,17,175,74,24,35,45,8,24,95,51,30,7,6,43,37,182,95,2,3,19,19,27,45,77,48,129,14,115,57,54,87,12,17,30,204,45,189,6,42,10,1,11,120,217,6,98,39,33,13,227,30,40,75,232,139,184,50,37,36,25,61,189,31,105,1,184,178,192,95,72,89,7,166,77,150,15,10,7,21,27,10,34,6,76,1,65,180,15,102,128,120,94,29,200,23,35,55,1,61,53,108,75,9,20,77,7,21,12,74,105,98,77,6,18,162,1,21,47,101,38,6,25,31,77,44,96,31,10,9,13,38,2,32,80,35,8,8,17,54,152,53,2,124,13,178,92,13,128,1,3,69,48,106,12,12,42,16,1,23,78,13,77,195,38,6,73,131,5,59,2,23,73,26,22,72,177,19,27,43,8,27,151,1,98,72,15,4,4,1,34,99,148,39,27,66,51,184,49,75,165,129,130,167,50,1,18,79,158,13,54,34,74,7,86,20,84,138,113,30,127,128,107,64,121,140,102,3,45,34,175,122,77,186,2,143,2,144,9,114,55,56,35,103,127,16,143,8,1,136,11,182,12,118,170,149,18,28,56,106,89,41,142,45,12,11,34,26,126,67,8,7,105,72,183,6,182,16,97,1,32,122,47,45,3,1,4,56,106,102,174,4,56,34,63,11,60,143,5,10,145,201,135,11,71,45,78,2,163,26,29,36,28,146,69,185,28,89,68,197,38,117,134,61,44,27,32,6,56,2,103,1,147,36,146,95,49,42,69,84,17,5,48,90,166,139,17,10,22,43,3,30,31,145,127,54,31,1,79,42,33,14,31,80,18,89,244,60,4,80,135,125,46,55,82,121,30,15,54,120,113,55,4,1,15,14,1,23,3,44,15,170,23,51,87,30,6,64,62,6,6,117,186,137,27,35,108,165,111,29,160,12,10,81,6,36,2,51,75,3,80,8,40,62,91,5,59,153,144,66,106,7,118,166,25,149,35,52,10,35,38,2,36,59,7,9,14,147,69,93,141,36,74,11,14,16,31,20,8,21,10,80,65,169,214,8,8,28,8,135,9,21,40,9,86,42,33,153,16,56,186,107,71,19,62,183,79,109,8,14,19,114,46,145,58,46,5,28,2,80,2,94,55,89,5,123,10,167,5,6,11,37,50,19,29,4,13,48,40,5,18,51,88,37,72,64,1,45,36,115,203,163,14,6,3,12,17,105,143,49,78,113,49,9,88,41,97,110,20,88,129,32,1,186,89,54,104,220,130,137,56,206,131,5,31,54,182,50,36,61,7,15,102,61,23,84,60,86,100,144,16,67,31,70,129,1,63,11,114,26,92,209,18,8,43,149,136,150,73,124,42,52,53,53,22,47,56,117,27,45,38,42,98,33,54,123,1,120,12,116,31,72,40,18,31,30,12,3,107,47,31,61,148,20,43,27,2,65,104,2,44,176,27,4,197,134,154,71,115,54,1,80,12,9,11,140,31,165,97,39,8,51,100,19,52,5,196,77,106,20,1,14,149,103,173,150,160,117,33,14,205,2,105,188,11,85,17,99,29,123,163,27,3,78,76,52,83,16,49,9,17,69,172,64,42,61,197,103,125,2,36,34,114,172,8,59,64,20,78,72,135,79,56,9,51,15,34,101,61,20,36,79,69,42,25,104,22,29,29,38,21,78,122,89,20,9,191,8,4,208,1,111,68,64,17,48,25,8,14,189,42,10,121,24,117,21,124,197,91,20,82,165,26,18,143,41,58,59,39,59,95,91,15,26,130,28,155,64,34,33,95,92,44,181,4,78,85,95,33,128,7,89,103,180,9,19,176,3,3,132,28,39,1,203,15,62,116,89,96,180,9,75,98,24,80,46,7,43,24,53,170,130,47,38,144,3,55,1,136,1,9,36,111,1,195,1,30,8,60,3,157,79,44,20,64,8,125,102,199,51,50,2,13,151,1,24,74,10,11,112,20,154,1,109,66,85,124,61,97,16,145,98,127,25,41,201,96,72,117,80,40];
B=[71,230,77,92,236,212,207,3,110,100,74,131,216,144,15,174,143,154,79,137,100,133,203,243,28,18,89,250,116,185,163,177,17,40,148,2,27,13,48,204,61,5,115,206,20,61,116,233,199,33,38,11,242,236,66,61,228,110,47,9,114,125,193,19,225,200,147,201,183,29,192,118,245,212,181,151,181,32,132,53,112,79,57,150,8,26,40,238,43,40,21,101,141,119,250,207,201,58,233,4,249,143,104,62,198,198,80,132,135,76,26,239,79,29,129,115,177,99,135,126,154,118,15,51,41,206,137,29,137,20,23,53,98,95,53,221,40,145,192,151,93,22,44,47,213,47,217,202,237,79,77,82,245,236,22,105,88,41,176,242,86,244,169,247,231,195,93,166,55,90,193,230,73,223,29,212,233,231,198,132,169,131,210,159,207,86,188,53,49,244,29,76,52,242,164,177,237,191,241,193,146,108,219,202,30,133,75,29,69,178,162,146,118,153,127,67,35,30,141,155,130,132,10,48,245,8,37,97,200,192,85,100,83,95,46,126,43,91,20,47,130,10,200,169,41,158,118,170,219,204,150,5,170,14,226,191,22,230,12,5,138,63,179,22,55,89,28,27,174,178,20,112,200,129,42,174,167,10,79,21,159,133,45,58,96,233,222,137,67,29,103,189,234,168,82,94,11,8,105,155,240,216,47,36,78,60,217,57,153,193,209,136,230,81,133,29,234,240,80,184,142,120,14,127,28,148,174,152,243,188,206,126,158,165,198,140,192,135,53,230,153,80,222,11,194,3,169,66,117,201,134,101,139,147,70,170,16,50,188,130,228,81,245,172,184,179,51,65,241,182,127,244,52,36,16,182,27,160,180,16,76,108,121,211,20,232,23,135,7,213,243,100,98,200,3,108,194,218,142,206,6,88,35,106,94,90,202,11,14,221,224,247,25,164,209,231,14,248,66,53,160,55,186,185,236,40,141,75,213,237,193,135,85,83,81,103,129,238,27,149,101,169,184,177,217,126,146,81,158,175,11,161,147,230,230,44,76,34,178,5,155,34,213,206,80,55,2,188,90,224,20,196,84,38,181,250,98,21,128,148,236,48,62,227,194,37,66,85,173,181,86,95,220,194,169,3,36,180,163,118,197,28,67,230,58,128,93,110,47,89,178,200,159,38,181,244,177,129,55,224,216,26,222,20,92,84,92,221,46,206,128,193,128,178,7,203,195,225,72,146,19,205,243,165,172,131,236,64,126,63,142,50,123,243,18,129,200,181,166,228,88,110,161,82,102,120,65,100,123,24,110,103,174,248,112,134,212,61,163,179,125,92,51,166,137,215,225,92,73,214,146,133,89,213,230,227,166,107,55,100,120,68,156,189,221,27,106,5,167,5,124,106,210,57,151,141,222,97,40,31,91,97,52,34,8,89,86,112,229,19,167,135,140,119,170,8,85,214,158,231,177,107,130,6,153,60,230,201,249,156,114,73,10,108,53,121,146,91,183,172,135,73,194,154,93,163,228,147,227,125,228,181,58,39,236,242,58,37,88,47,27,149,64,160,103,97,129,234,166,36,180,140,89,202,11,72,79,202,156,167,241,107,17,177,183,167,234,105,202,50,85,84,83,24,124,78,238,55,123,210,45,181,229,190,127,47,204,44,186,39,149,147,176,33,78,30,13,149,115,61,143,196,204,130,91,239,88,108,20,63,199,33,15,215,159,225,93,177,209,8,152,17,28,29,173,148,194,105,152,93,104,121,22,70,6,224,98,111,110,2,34,223,167,248,164,227,244,174,158,221,3,172,199,238,107,47,143,51,223,201,126,16,203,135,216,128,94,119,87,31,89,222,108,51,79,234,167,133,3,97,85,232,197,174,105,89,112,230,177,149,90,122,39,173,227,53,139,103,24,114,152,71,73,153,117,147,107,32,189,63,206,175,149,219,14,240,10,46,231,20,117,103,136,212,105,38,39,66,245,75,54,145,26,128,60,233,211,203,46,136,225,78,145,189,155,66,74,45,190,145,172,130,193,140,210,230,116,43,124,189,159,59,247,7,247,125,152,45,145,8,115,108,186,22,66,248,21,245,219,159,156,3,208,195,124,151,241,191,211,107,169,150,28,124,184,10,114,26,100,181,202,178,124,198,172,121,19,153,2,131,60,193,3,220,2,133,56,129,208,216,186,194,81,126,195,138,243,212,124,128,36,41,170,2,119,164,187,103,131,37,182,62,187,106,222,199,81,135,27,223,151,147,190,174,232,130,78,123,82,212];